class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        left, right = -1, m * n
        while left + 1 < right:
            mid = (left + right) // 2
            x = matrix[mid // n][mid % n]
            if x == target:
                return True
            if x < target:
                left = mid
            else:
                right = mid
        return False


'''
def serachLine(matrix, target):# 找到行号
    m, n = len(matrix), len(matrix[0])
    top, bottom = 0, m - 1
    while top <= bottom:
        mid = (top + bottom)// 2
        if matrix[mid][0] < target:
            top = mid + 1
        else:
            bottom = mid - 1
    return top if m == 2 else bottom
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        row = serachLine(matrix, target)
        if row >= len(matrix):
            return False
        for i in range(len(matrix[0])): # 对每行进行遍历
            if matrix[row][i] == target:
                return True
        return False
'''